package com.ashin.dp;

import java.util.Arrays;

/**
 * @Author: Ashin
 * @Date: 2020/9/4
 * @Description: com.ashin
 * @Version: 1.0.0
 */
public class KMP {


    public static void main(String[] args) {
        String pattern = "abababbbabbbbababa";
        System.out.println(Arrays.toString(myNext(pattern)));
        System.out.println(Arrays.toString(next(pattern)));
        System.out.println(Arrays.toString(nextEnhance(pattern)));
    }

    /**
     * 自己实现的求next函数算法，个人觉得这个写法更符合感官直觉。但是时间复杂度比较高，
     *
     * @param pattern
     * @return
     */
    public static int[] myNext(String pattern) {
        int[] next = new int[pattern.length()];

        next[0] = -1;
        for (int cursorIdx = 1; cursorIdx < next.length; cursorIdx++) {
            //获取当前不相等字符的前面的字符串
            String prefixStr = pattern.substring(0, cursorIdx);

            //下面的循环求最长公共前后缀的长度，即当前next[i]的nextVal
            int nextVal = 0;
            for (int j = 0, len = prefixStr.length() - 1; j < len; j++) {
                //前前缀是否等于后缀，如果相等，则获取当前的长度
                if (prefixStr.substring(0, j + 1).equals(prefixStr.substring(prefixStr.length() - j - 1))) {
                    nextVal = prefixStr.substring(0, j + 1).length();
                }
            }

            next[cursorIdx] = nextVal;
        }

        return next;
    }

    /**
     * 无法理解这种写法，脑壳疼
     *
     * @param pattern
     * @return
     */
    public static int[] next(String pattern) {
        int i = 0;
        int j = -1;
        int[] next = new int[pattern.length()];
        next[0] = -1;
        int times = 0;
        while (i < next.length - 1) {
            System.out.println(String.format("第%s次循环,i=%d,j=%d", times++, i, j));
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                ++i;
                ++j;

                next[i] = j;


            } else {
                j = next[j];
            }
        }

        return next;
    }

    public static int[] nextEnhance(String pattern) {
        int i = 0;
        int j = -1;
        int[] next = new int[pattern.length()];
        next[0] = -1;
        while (i < next.length - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (pattern.charAt(i) == pattern.charAt(j)) {
                    next[i] = next[j];
                } else {
                    next[i] = j;
                }

            } else {
                j = next[j];
            }
        }

        return next;
    }


}
